from typing import Optional
# from DataStructure.Tree import TreeNode


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
        xf, yf = None, None
        rootf = TreeNode(val=-1, left=root)
        queue = [(rootf,-1)]
        while queue:
            node, height = queue.pop()
            if node.left is not None:
                queue.append((node.left, height+1))
                if node.left.val == x:
                    xf = (node.val, height+2)
                if node.left.val == y:
                    yf = (node.val, height+2)
            
            if node.right is not None:
                queue.append((node.right, height+1))
                if node.right.val == x:
                    xf = (node.val, height+2)
                if node.right.val == y:
                    yf = (node.val, height+2)
            
            if xf is not None and yf is not None:
                return xf[1]==yf[1] and xf[0] != yf[0]

if __name__ == '__main__':
    def bfs_load(l):
        if l:
            root = TreeNode(l[0])
            l = l[1:]
            queue = [root]
            while l:
                if l[0] is not None:
                    queue[0].left = TreeNode(l[0])
                    queue.append(queue[0].left)
                l = l[1:]
                if l:
                    if l[0] is not None:
                        queue[0].right = TreeNode(l[0])
                        queue.append(queue[0].right)
                    l = l[1:]
                    queue = queue[1:]
                else:
                    break
            return root
    
    l = bfs_load([1,2,3,4])
    s = Solution()
    print(s.isCousins(l, 3,4))
    